import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


public class Leetcode102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return List.of();
        }

        Deque<TreeNode> deque = new ArrayDeque<>();
        Deque<TreeNode> level = new ArrayDeque<>();
        deque.add(root);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> currentLevelRes = new ArrayList<>();
        while (!deque.isEmpty()) {
            TreeNode treeNode = deque.pop();
            currentLevelRes.add(treeNode.val);
            if (treeNode.left != null) {
                level.add(treeNode.left);
            }

            if (treeNode.right != null) {
                level.add(treeNode.right);
            }

            if (deque.isEmpty()) {
                deque.addAll(level);
                level.clear();
                res.add(currentLevelRes);
                currentLevelRes = new ArrayList<>();
            }
        }

        return res;
    }
}
